#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

/**
  * @方法: 双指针
  * @时间复杂度: o(n^2)
  * @空间复杂度: o(1)
  * @评价: max_int 的一半小一点 0x3f3f3f3f
*/
int threeSumClosest(vector<int>& nums, int target) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int best = 0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        int j = i+1;
        int k = n-1;
        while(j < k){
            int sum = nums[i] + nums[j] + nums[k];
            if(sum == target) return target;
            best = (abs(sum - target) < abs(best - target)) ? sum : best;
            if(sum > target){
                --k;
            }else{
                ++j;
            }
        }
    }
    return best;
}